package q29_divide;

public class Solution_3 {
    public static void main(String[] args) {

    }

    /**
     * 最快的方法
     * 很明显, 对于一次次减是不可行的, 但咱们可以减除数的2倍,然后结果+2,4倍+4...... 故不停的左移除数, 直到其大于被除数的一半,
     * 然后减去, 右移除数使其小于被除数,减去......依次类推, 直到被除数小于原始除数.
     * @param dividend
     * @param divisor
     * @return
     */
    public int divide(int dividend, int divisor) {
        // 先除掉特殊案例
        boolean fu = (((dividend >>> 31) ^ (divisor >>> 31)) == 1);
        // 然后都转为负数
        if(dividend > 0) dividend = -dividend;
        if(divisor > 0) divisor = -divisor;
        // 一开始，先设置一个被除数的一半
        int mod = divisor;
        int minn = dividend >> 1;
        int now = -1;

        // 如果除数大于被除数的一半（从数轴上来看，实际上绝对值是小于被除数的一半），则将mod和now一直*2
        // now是用来记录答案的，随着反复mod的操作也一起*2 之后还有不断累加
        while(mod >= minn) {
            mod <<= 1;
            now <<= 1;
        }


        // 这里建议还是画一个数轴，一开始diviend减去了一个一个大于自己一半的数，然后用剩下的一段继续比较divisor，如果小于就直接结束了
        // 如果没有，则用mod来比较减掉一段的diviend，如果比他大，则之后**所需要累加的now就要除以2，mod也除以2**
        // 直到小于，则继续减去mod，然后循环，最终得到答案
        int ans = 0;
        while(dividend <= divisor){
            while(mod < dividend){
                mod >>= 1;
                now >>= 1;
            }
            while(dividend <= mod) {
                dividend -= mod;
                ans-=now;
            }
        }
        if(ans == -2147483648 && !fu) return 2147483647;
        return fu?-ans:ans;
    }
}
